Universal hash function

A random hash function $h: \mathcal{U} \rightarrow \{1,…,m\}$ is universal if, for any fixed $x,y \in \mathcal{U}$, $$\mathrm{Pr}[h(x)=h(y)] \leq \frac{1}{m}$$

Efficient construction: Let $p$ be a prime number between $|\mathcal{U}|$ and $2|\mathcal{U}|$. Let $a$, $b$ be random numbers in $0,…,p$, $a \neq 0$. $$h(x) = [a \cdot x + b \pmod p] \pmod m$$ is universal.

See also: Hashing Compare: Uniformly Random Hash Function